#include <vector>
#include <iostream>

using namespace std;

class BST
{
    // 注意这里的 public，简单起见，我们暂时把类的所有属性和方法都定义成
    // public，方便使用。
public:
    // 定义普通属性
    int value;

    // 定义指针属性
    BST *left;
    BST *right;

    // 每一个 class 都有一个和 class 同名类型的函数，叫做构造函数。
    // 它决定了创建对象的方法。
    // 例如，我们的 BST 接受一个整数，于是创建 BST 对象的时候，
    // 我们可以写 BST(10)
    // 接下来，在 构造函数的 () 后面，我们用 : 定义 成员初始化列表。
    // 在初始化列表里，我们要给每一个属性设置初始值。
    BST(int v = 0) : value(v), left(nullptr), right(nullptr)
    {
        cout << "BST: value(" << value << ")" << endl;
    }

    int max()
    {
        BST *pos = this;
        while (pos->right != nullptr)
        {
            pos = pos->right;
        }

        return pos->value;
    }

    void insert(int v)
    {
        // 这里，要理解 this 在类方法中的含义，简单地说，
        // 谁调用 insert，这里的 this 就代表谁。
        BST *pos = this;

        // 可以直接挂在右边的情况
        // 注意我们如何通过一个指针访问类对象的属性，要使用 -> 操作符
        if (pos->right == nullptr && v >= pos->value)
        {
            // 让指针指向一个新对象的时候，必须使用 new 操作符创建对象。
            pos->right = new BST(v);
            return;
        }

        // 可以直接挂在左边的情况
        if (pos->left == nullptr && v < pos->value)
        {
            pos->left = new BST(v);
            return;
        }

        // 需要向右边继续探索的情况
        if (v >= pos->value)
        {
            right->insert(v);
        }
        else
        {
            // 需要向左边继续探索的情况
            left->insert(v);
        }
    }
};

int main(int argc, char const *argv[])
{

    vector<int> v{2, 3, 8, 9, 6, 5, 7};

    BST root(v[0]);

    for (int i = 1; i < v.size(); ++i)
    {
        root.insert(v[i]);
    }

    cout << root.max() << endl;

    return 0;
}
